#include "main/utils.h"
#include "lib/list.h"
using namespace std;

ListNode* split(ListNode* phead) {
  auto fast = phead->next;
  auto slow = phead;
  while (fast && fast->next) {
    fast = fast->next->next;
    slow = slow->next;
  }
  auto ret = slow->next;
  slow->next = nullptr;
  return ret;
}

ListNode* mergeList(ListNode* head1, ListNode* head2) {
  ListNode* phead = CreateNode(0);
  auto cur_node = phead;
  while (head1 && head2) {
    if (head1->value < head2->value) {
      cur_node->next = head1;
      head1 = head1->next;
    } else {
      cur_node->next = head2;
      head2 = head2->next;
    }
    cur_node = cur_node->next;
  }

  if (head1) {
    cur_node->next = head1;
  } else {
    cur_node->next = head2;
  }
  return phead->next;
}

ListNode* sortList(ListNode* phead) {
  if (!phead || !phead->next)
    return phead;
  auto head1 = phead;
  auto head2 = split(phead);

  head1 = sortList(head1);
  head2 = sortList(head2);

  return mergeList(head1, head2);
}

int main() {
  vector<int> nums = {3, 5, 1, 4, 2, 6};
  auto phead = CreateList(nums);
  auto ret = sortList(phead);
  PrintList(ret);

  return 0;
}
